import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;


public class GrahamScan {

	public static void main(String[] args) {
		GrahamScan grahamScan = new GrahamScan();
		
		for (int i = 1; i < 7; i++) {
			String filename = "case" + i + ".txt";
			ArrayList<Point> points = PointUtil.readPointDataFile(filename);
			
			grahamScan.findConvexHull(points, filename);
		}

	}
	
	private void findConvexHull(ArrayList<Point> points, String filename) {
		
		// Step 1:  Sort by asc Y-coord.  This puts the min Y at index=0
		Collections.sort(points, new PointYOrder());
		
		// Step 2:  Sort by polar angle relative to min Y-coord.  
		// 			NOTE: collinear pts aren't removed here due to 
		//			Java sort-comparator limitations.  Collinearpts are removed in the CH loop below
		Collections.sort(points, new PolarOrder(points.get(0)) );
		System.out.println("\n          "+ filename + " points:" + points);
		
		// Step 3:  Iterate over points and identify those composing convex hull
		
		// ArrayList is used as the CH "stack"
		ArrayList<Point> hullPoints = new ArrayList<Point>();
		Iterator<Point> iter = points.iterator();
		hullPoints.add(iter.next()); // i.e. "push" first 3 points
		hullPoints.add(iter.next());
		hullPoints.add(iter.next());
		
		// 3.1 Make sure first three pts aren't collinear.  If so, remove middle pt
		if ( PointUtil.isCollinear(	hullPoints.get(0), hullPoints.get(1), hullPoints.get(2)) )
		{
			hullPoints.remove(1);
		}
		
		// 4 Iterate points.  Identify CH
		while (iter.hasNext()) {
			Point nextPoint = iter.next();
			// Remove from hull if this next point is collinear or non-left turn
			while ( !PointUtil.isLeftTurn(
							hullPoints.get(hullPoints.size()-2), 
							hullPoints.get(hullPoints.size()-1),
							nextPoint)   
					||
					PointUtil.isCollinear(
							hullPoints.get(hullPoints.size()-2), 
							hullPoints.get(hullPoints.size()-1),
							nextPoint)    ) 
			{
				hullPoints.remove(hullPoints.size()-1);  // i.e. "pop" non-CH point
			}
			hullPoints.add(nextPoint);  // i.e. "push" CH point
		}
		
		// hullPoints now contains the CH points
		System.out.println("case " + filename + " convex hull:" +hullPoints);
	}

}
